/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    // 递归法 
    ListNode* ReverseList(ListNode* p) {
        if(!p||!p->next) {
            return p;
        }
        ListNode* ans = ReverseList(p->next);
        p->next->next = p;
        p->next = nullptr;
        return ans;
    }
    /*
    ListNode* ReverseList(ListNode* p) {
        return Reverse(p, nullptr);
    }
    ListNode* Reverse(ListNode* cur, ListNode* prev) {
        if(!cur) return prev;
        ListNode* tmp = cur -> next;
        cur->next = prev;
        prev = cur;
        cur = tmp;
        return Reverse(cur, prev);
    }
    */
    
    /*
    // 双指针法
    ListNode* ReverseList(ListNode* p) {
        ListNode* prev = nullptr, *cur = p;
        ListNode* next;
        while(cur) {
            next = cur -> next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    */
};